package com.dai.code;

import com.dai.common.Node;

/**
 * 链表相交
 *
 * @author daijiyong
 */
public class LinkedListCross {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node temp = node1;
        for (int i = 2; i < 10; i++) {
            temp.next = new Node(i);
            temp = temp.next;
        }
        Node node2 = new Node(1);
        temp = node2;
        for (int i = 2; i < 6; i++) {
            temp.next = new Node(i);
            temp = temp.next;
        }
        temp.next = node1.next.next.next.next;
        System.out.println(isLinkedListCross(node1, node2));
        System.out.println(findLinkedListCross(node1, node2));
        System.out.println(findLinkedListCross2(node1, node2));
        System.out.println(findLinkedListCross3(node1, node2));
    }

    public static Boolean isLinkedListCross(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1 == node2) {
            return true;
        }
        // 同时遍历两个链表，如果最后一个节点是同一个，那么肯定相交
        while (node1.next != null || node2.next != null) {
            if (node1.next != null) {
                node1 = node1.next;
            }
            if (node2.next != null) {
                node2 = node2.next;
            }
        }

        return node1 == node2;
    }

    public static Node findLinkedListCross(Node node1, Node node2) {
        Node head1 = node1;
        Node head2 = node2;

        // 循环遍历，总归会相交，第一次相交点就是node1和node2第一次相等的时候
        while (node1 != node2) {
            node1 = node1 == null ? head1 : node1.next;
            node2 = node2 == null ? head2 : node2.next;
        }

        return node1;
    }
    public static Node findLinkedListCross2(Node node1, Node node2) {
        Node head1 = node1;
        Node head2 = node2;

        // 循环遍历，两遍下来，
        // 遍历的路程肯定是一样的，除去最后相交的那一段，第一个相等点就是相交点
        while (node1 != node2) {
            node1 = node1 == null ? head2 : node1.next;
            node2 = node2 == null ? head1 : node2.next;
        }

        return node1;
    }

    public static Node findLinkedListCross3(Node node1, Node node2) {
        int len1 = 0;
        int len2 = 0;

        //对比两条链表的长度
        Node temp1 = node1;
        Node temp2 = node2;
        while (temp1 != null) {
            len1++;
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            len2++;
            temp2 = temp2.next;
        }
        // 将两条链表截成等长
        temp1 = node1;
        temp2 = node2;
        if (len1 > len2) {
            for (int i = 0; i < len1 - len2; i++) {
                temp1 = temp1.next;
            }
        } else if (len1 < len2) {
            for (int i = 0; i < len2 - len1; i++) {
                temp2 = temp2.next;
            }
        }
        // 遍历等长的相交链表，第一次节点相等，即为相交点
        while (temp1 != temp2) {
            temp1 = temp1.next;
            temp2 = temp2.next;
        }
        return temp1;
    }
}